package cn.fansunion.leecode.subArray;
/**
 * 53. 最大子数组和
 * https://leetcode-cn.com/problems/maximum-subarray/
 * @author wen.lei@brgroup.com
 *
 * 2021-12-25
 */
public class MaxSubArray {

    /**
     * 雷:这个方法的关键点 核心理解；如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字 <br/>
     * 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字 <br/>
     * 抽象了3个变量值：当前遍历num、当前求和、当前求和sum和num比较、sum和当前最大sum比较
     * 
     * @param nums
     * @return
     */
    // 作者：guanpengchn
    // 链接：https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
    // 来源：力扣（LeetCode）
    // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public static int maxSubArray(int[] nums) {
        int currentMaxSum = nums[0];
        int sum = 0;
        for (int num : nums) {
            //如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留
            if (sum > 0) {
                sum += num;
            } 
            //如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃
            else {
                sum = num;
            }
            currentMaxSum = Math.max(currentMaxSum, sum);
        }
        return currentMaxSum;
    }

}
